package implementation.sort.QuickSort;

import anaydis.sort.SorterType;
import com.sun.istack.internal.NotNull;
import com.sun.org.apache.xerces.internal.util.IntStack;

import java.util.Comparator;
import java.util.List;

public class QuickSortNonRecursive extends QuickSorter {

    public QuickSortNonRecursive() {
        super(SorterType.QUICK_NON_RECURSIVE);
    }

    public <T> void sort(@NotNull Comparator<T> tComparator, @NotNull List<T> ts) {
        sort(tComparator, ts, 0, ts.size() - 1);
    }


    private <T> void sort(Comparator<T> comparator, List<T> list, int start, int end) {
        IntStack stack = new IntStack();
        stack.push(start);
        stack.push(end);
        while (stack.size() > 0) {
            end = stack.pop();
            start = stack.pop();
            if (end <= start) {
                continue;
            }
            int i = partition(comparator, list, start, end);
            if (i - start > end - i) {
                stack.push(start);
                stack.push(i - 1);
            }
            stack.push(i + 1);
            stack.push(end);
            if (end - i >= i - start) {
                stack.push(start);
                stack.push(i - 1);
            }
        }
    }

}